UVa12345 Dynamic len(set(a[L:R])) <带修莫队>

Posted on Symbols count in article: 839 Reading time ≈ 3 mins.

Problem

Dynamic len(set(a[L:R]))

Description

In python, we can use len(start(a[L:R])) to calculate the number of distinct values of elements a[L],a[L+1],⋯ ,a[R−1]a[L],a[L + 1], \cdots,a[R-1].
Tere are some interactive examples that may help you understand how it is done. Remember that the indices of python lists start from 00.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
>>>
a=[1,2,1,3,2,1,4]
>>> print a[1:6]
[2, 1, 3, 2, 1]
>>> print set(a[1:6])
set([1, 2, 3])
>>> print
len(set(a[1:6]))
3
>>> a[3]=2
>>> print
len(set(a[1:6]))
2
>>> print len(set(a[3:5]))
1

Your task is to simulate this process.

Input

There will be only one test case. The first line contains two integers nn and mm (1≤n,m≤50,000)(1\le n,m\le 50,000).
The next line contains the original list.
All the integers are between 11 and 1,000,0001,000,000 (inclusive). The next m lines contain the statements
that you need to execute.
A line formatted as ‘MM xx yy’ (1≤y≤1,000,000)(1\le y\le 1,000,000) means a[x]=ya[x] = y, and a line formatted as ‘QQ xx
yy’ means print len(set(a[x:y]))print\ len(set(a[x : y])).
It is guaranteed that the statements will not cause indexindex outout ofof rangerange error.

Output

Print the simulated result, one line for each query.

Sample Input

1
2
3
4
5
6
7 4
1 2 1 3 2 1 4
Q 1 6
M 3 2
Q 1 6
Q 3 5

Sample Output

1
2
3
3
2
1

标签：带修莫队

Translation

给出一个长为nn的序列，有mm个操作，分为两类：

  1. QQ aa bb 询问此序列a∼ba\sim b位间有多少种不同数
  2. MM aa bb 将第aa位改为bb。

Solution

本题数据范围只有五万，一看就是带根号的算法，可以O(nn)O(n\sqrt{n})莫队水过。
我们发现QQ操作是标准莫队，但MM操作是修改，因而需用带修莫队。
带修莫队即在普通莫队的双指针种再加一个指针，指向时间。对于离线后询问建的扩展，如果是同一时间，就直接移动双指针；如果是不同时间，就先暴力移动时间指针，然后再移双指针即可。
暴力出奇迹~~~

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define MAX_N 50000
#define MAX_C 1000000
using namespace std;
int n, m, tmp, col[MAX_N+5];
int cnt[MAX_C+5], pos[MAX_N+5], lst[MAX_N+5], ans[MAX_N+5];
bool mark[MAX_N+5];
struct Modify {int pos, x, pre;} M[MAX_N+5];
struct Query {int l, r, id, ts;} Q[MAX_N+5];
bool cmp(const Query &a, const Query &b) {
    return	pos[a.l] < pos[b.l] || 
            (pos[a.l] == pos[b.l] && pos[a.r] < pos[b.r]) || 
            (pos[a.l] == pos[b.l] && pos[a.r] == pos[b.r] && a.ts < b.ts);
}
void add(int x) {
    if (mark[x]) {
        cnt[col[x]]--;
        if (!cnt[col[x]])	tmp--;
    } else {
        if (!cnt[col[x]])	tmp++;
        cnt[col[x]]++;
    }
    mark[x] ^= 1;
}
void change(int x, int y) {
    if (mark[x])	add(x), col[x] = y, add(x);
    else	col[x] = y;
}
int main() {
    scanf("%d%d", &n, &m);
    int magic = (int)(sqrt((double)n+0.5));
    int tot = 0, ind = 0;
    for (int i = 1; i <= n; i++)	scanf("%d", &col[i]), lst[i] = col[i], pos[i] = i/magic;
    for (int i = 1; i <= m; i++) {
        char opt[2];
        int x, y;
        scanf("%s%d%d", opt, &x, &y);	x++;
        if (opt[0] == 'Q') {
            Q[++tot].id = tot;
            Q[tot].l = x, Q[tot].r = y, Q[tot].ts = ind;
        } else {
            M[++ind].pos = x, M[ind].x = y, M[ind].pre = lst[x];
            lst[x] = y;
        }
    }
    sort(Q+1, Q+tot+1, cmp);
    int now = 0, l = 1, r = 0;
    for (int i = 1; i <= tot; i++) {
        if (now < Q[i].ts)	for (int j = now+1; j <= Q[i].ts; j++)	change(M[j].pos, M[j].x);
        if (now > Q[i].ts)	for (int j = now; j > Q[i].ts; j--)	change(M[j].pos, M[j].pre);
        if (l > Q[i].l)	for (int j = l-1; j >= Q[i].l; j--)	add(j);
        if (r < Q[i].r)	for (int j = r+1; j <= Q[i].r; j++)	add(j);
        if (l < Q[i].l)	for (int j = l; j < Q[i].l; j++)	add(j);
        if (r > Q[i].r)	for (int j = r; j > Q[i].r; j--)	add(j);
        now = Q[i].ts, l = Q[i].l, r = Q[i].r;
        ans[Q[i].id] = tmp;
    }
    for (int i = 1; i <= tot; i++)	printf("%d\n", ans[i]);
    return 0;
}